package tree;

/**
 * 给你一棵以 root 为根的二叉树和一个整数 target ，请你删除所有值为 target 的 叶子节点 。
 * <p>
 * 注意，一旦删除值为 target 的叶子节点，它的父节点就可能变成叶子节点；如果新叶子节点的值恰好也是 target ，那么这个节点也应该被删除。
 * <p>
 * 也就是说，你需要重复此过程直到不能继续删除。
 * <p>
 * 示例 1：
 * 输入：root = [1,2,3,2,null,2,4], target = 2
 * 输出：[1,null,3,null,4]
 * 解释：
 * 上面左边的图中，绿色节点为叶子节点，且它们的值与 target 相同（同为 2 ），它们会被删除，得到中间的图。
 * 有一个新的节点变成了叶子节点且它的值与 target 相同，所以将再次进行删除，从而得到最右边的图。
 * <p>
 * 示例 2：
 * 输入：root = [1,3,3,3,2], target = 3
 * 输出：[1,3,null,null,2]
 * <p>
 * 示例 3：
 * 输入：root = [1,2,null,2,null,2], target = 2
 * 输出：[1]
 * 解释：每一步都删除一个绿色的叶子节点（值为 2）。
 *
 * @author Jisheng Huang
 * @version 20250423
 */
public class DelLeavesWithAGivenVal_1325 {
    /**
     * 给你一棵以 root 为根的二叉树和一个整数 target ，请你删除所有值为 target 的 叶子节点 。
     *
     * @param root   the given root node
     * @param target the value to be removed from the given treenode
     * @return a treenode with all the target value being removed
     */
    public static TreeNode removeLeafNodes(TreeNode root, int target) {
        TreeNode dummyNode = new TreeNode(Integer.MAX_VALUE, root, null);
        dfs(root, dummyNode, target, true);

        return dummyNode.left;
    }

    public static void dfs(TreeNode root, TreeNode parent, int target, boolean leftDirection) {
        if (root == null) {
            return;
        }

        dfs(root.left, root, target, true);
        dfs(root.right, root, target, false);

        // Arrive leaf node
        if (root.left == null && root.right == null && root.val == target) {
            unlinkNode(parent, leftDirection);
        }
    }

    public static void unlinkNode(TreeNode parent, boolean leftDirection) {
        if (leftDirection) {
            parent.left = null;
        } else {
            parent.right = null;
        }
    }


    /**
     * Private inner TreeNode class
     */
    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
